// memory.c
#include <stdio.h>
#include <stdlib.h>

#define MEM_SIZE 8096

typedef struct Block {
    size_t size;
    struct Block* next;
} Block;

static char mem[MEM_SIZE];
static Block* freeList = NULL;

void initialize() {
    freeList = (Block*)mem;
    freeList->size = MEM_SIZE - sizeof(Block);
    freeList->next = NULL;
}

void* umalloc(size_t size) {
    if (size <= 0 || size > MEM_SIZE) {
        return NULL; // Invalid size
    }

    Block *prev = NULL, *current = freeList;

    // Find the first block that is large enough
    while (current && (current->size < size)) {
        prev = current;
        current = current->next;
    }

    if (!current) {
        return NULL; // Not enough memory
    }

    // If the block is larger than needed, split it
    if (current->size > size + sizeof(Block)) {
        Block* newBlock = (Block*)((char*)current + size + sizeof(Block));
        newBlock->size = current->size - size - sizeof(Block);
        newBlock->next = current->next;
        current->size = size;
        current->next = newBlock;
    }

    // Remove the block from the free list
    if (prev) {
        prev->next = current->next;
    } else {
        freeList = current->next;
    }

    return (char*)current + sizeof(Block);
}

void ufree(void* ptr) {
    if (!ptr) {
        return; // Null pointer
    }

    Block* block = (Block*)((char*)ptr - sizeof(Block));
    block->next = freeList;
    freeList = block;
}

void umerge() {
    Block *prev = NULL, *current = freeList;

    // Merge consecutive free blocks
    while (current) {
        if (prev && ((char*)prev + prev->size + sizeof(Block) == (char*)current)) {
            // Merge current with the previous block
            prev->size += current->size + sizeof(Block);
            prev->next = current->next;
            current = prev;
        }
        prev = current;
        current = current->next;
    }
}

int main() {
    initialize();

    // Test memory allocation and deallocation
    printf("umalloc(1000,2000,500);\n");
    void* ptr1 = umalloc(1000);
    void* ptr2 = umalloc(2000);
    void* ptr3 = umalloc(500);

    printf("umerge();\n");
    umerge(); // Merge free blocks
    printf("ufree(ptr2=2000); ");
    ufree(ptr2); // Free a block
    printf("umerge(); ");
    umerge(); // Merge free blocks again

    printf("umalloc(800);\n");
    void* ptr4 = umalloc(800);
    printf("finish");
    return 0;
}
